#pragma once

#include <string>

namespace solution_044
{

class Solution
{
public:
    bool isMatch(std::string s, std::string p)
    {
        m_s.swap(s);
        m_p.swap(p);
        return match(0, 0);
    }

private:
    bool match(size_t s_first, size_t p_first)
    {
        /* find non-'*' substring in pattern */
        bool has_aster = false;
        while (p_first < m_p.size() && m_p.at(p_first) == '*') {
            has_aster = true;
            ++p_first;
        }
        auto p_last = p_first;
        while (p_last < m_p.size() && m_p.at(p_last) != '*')
            ++p_last;

        size_t len = p_last - p_first;
        if (len == 0)
            return s_first == m_s.size() || has_aster;

        if (has_aster) {
            while (s_first + len <= m_s.size()) {
                if (match_substring(p_first, p_last, s_first)) {
                    bool matched = match(s_first + len, p_last);
                    if (matched || p_last < m_p.size())
                        return matched;
                }
                ++s_first;
            }
            return false;
        } else {
            return s_first + len <= m_s.size() &&
                   match_substring(p_first, p_last, s_first) &&
                   match(s_first + len, p_last);
        }
    }

    bool match_substring(size_t p_first, size_t p_last, size_t s_first)
    {
        while (p_first < p_last) {
            if ( m_p.at(p_first) != '?' && m_p.at(p_first) != m_s.at(s_first) )
                return false;
            ++p_first;
            ++s_first;
        }
        return true;
    }

    std::string m_s;
    std::string m_p;
};

}  /* namespace solution_044 */
